package sort;

/**
 * Created by chucun on 2016/5/31.
 */
public class Insertsort {

    /**
     * 设数组为a[0…n-1]。
     * 1.      初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
     * 2.      将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
     * 3.      i++并重复第二步直到i==n-1。排序完成。
     */
    public static void insertsort1(int[] a, int n) {
        int i, j, k;
        for (i = 1; i < n; i++) {
            //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
            for (j = i - 1; j >= 0; j--) {
                if (a[j] < a[i]) {
                    break;
                }
            }

            //如找到了一个合适的位置
            if (j != i - 1) {
                //将比a[i]大的数据向后移
                int temp = a[i];
                for (k = i - 1; k > j; k--) {
                    a[k + 1] = a[k];
                }
                //将a[i]放到正确位置上
                a[k + 1] = temp;
            }

        }

    }
}
